package com.lmf.Stack.Calculator;

/**
 * 模拟实现一个计算器：利用栈实现，虽然结果都都正确，但是有一些小问题，会输出一些空提示
 */
public class CalculatorDemo {
    public static void main(String[] args) {
        //创建两个栈空间，一个存数，一个存符号
        ArrayStack numStack = new ArrayStack(10);
        //在栈中，是以整数形式存储的运算符，当char类型与整型比较时，会自动将char转换为int类型（Java自动类型转换）
        ArrayStack operStack = new ArrayStack(10);
        //被分析的表达式
        String expression = "7+3+5-1*3";
        //创建相关变量
        int index = 0;      //利用一个指针来遍历表达式
        int num1 = 0;       //作为从数栈取出的第二个数
        int num2 = 0;       //作为从数栈取出的第一个数
        int oper = 0;       //作为从字符栈取出的运算符，但是在栈中，是以整数形式存储的.
        int res = 0;
        char ch = ' ';      //每次扫描的char，保存到ch中
        String keepNum = ""; // 用于拼接多位数的

        //循环遍历分析整个表达式
        while (true){
            //获取表达式的第一个字符
            ch = expression.substring(index,index+1).charAt(0);

            //根据获取的字符，进行相应业务处理
            if (operStack.isOper(ch)){
                //如果是字符
                //1.如果字符栈为空，直接进栈
                if (operStack.isEmpty()) {
                    operStack.push(ch);
                }else {
                //2. 如果字符栈不为空
                    while (true){
                       //2.2 若字符的优先级小于等于已存在的字符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号,进行运算；将得到的结果,入数栈
                       // 然后再次判断 当前的操作符 与字符栈顶的操作符优先级，直到当前操作符优先级较大，或者成为字符栈中第一个操作符
                        if (operStack.priority(ch) <= operStack.priority(operStack.peak())) {
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            oper = operStack.pop();
                            //进行相应运算
                            res= operStack.cal(num1, num2, oper);
                            //将计算结果，重新存入数栈
                            numStack.push(res);
                        }else {
                            //再将新运算符，存入字符栈
                            operStack.push(ch);
                            break;
                        }
                    }
                }
            }else {
                // 如果是数字 则直接入数栈 注意这是字符  不是真正的数字
//                numStack.push(ch-48);

                // numStack.push(ch - 48);  这样子有问题 13 + 1 => '1' '3' '+' '1'
                // 在处理多位数时, 不能发现是一个数就立即入栈 因为他可能是多位数
                // 在处理数,需要向expression的表达式的index 后再看一位 , 如果是数 就进行扫描, 如果是符号才入栈
                // 因此我们需要定义一个变量 keepNum字符串 ,用于拼接多位数

                keepNum += ch;

                // 如果ch是expression的最后一位 直接入栈
                if (index == expression.length()-1){
                    numStack.push(ch - 48);
                }else {
                    // 判断下一个字符 是不是数组 ,就继续扫描 ,如果是运算符 则入栈
                    // 只看后一位 不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        // 如果后一位是运算符 则数字入栈
                        numStack.push(Integer.parseInt(keepNum));
                        // 重要的!!!!!! 清空keepNum
                        keepNum = "";
                    }
                }
            }

            //当表达式逐个分析到最后，结束循环
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        // 当表达式扫描完毕, 就顺序的从 数栈和符号栈中pop出相应的数和符号,并运行
        while (true){
            //如果符号栈为空,则计算到最后的结果 数字栈 只有一个结果
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            //进行相应运算
            res= operStack.cal(num1, num2, oper);
            //将计算结果，重新存入数栈
            numStack.push(res);
        }
        //打印结果
        System.out.println(expression+" = "+res);
    }
}

class ArrayStack{
    //数组最大空间
    private int maxSize;
    //创建一个数组
    private int[] stack;
    //创建一个指向数组顶端的指针
    private int top = -1;   //表示栈顶 初始化为-1

    //创建构造方法：初始化参数
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[this.maxSize];
    }

    //判断栈满的方法
    public boolean isFull(){
        return top == maxSize-1;
    }

    //判断栈空的方法
    public boolean isEmpty(){
        return top == -1;
    }

    //不改变原本栈的空间结构，获取栈顶端数据
    public int peak(){
        //判断是否为空
        if (this.isEmpty()) {
            System.out.println("栈空，没有数据！");
            return -1;
        }
        return stack[top];
    }

    //计算方法
    public int cal(int num1,int num2,int oper){
        int res = 0;
        switch (oper){
            case '*':
                res = num2*num1;    //注意顺序，数栈下面的数，运算时放在前面
                break;
            case '/':
                res = num2/num1;
                break;
            case '+':
                res = num2+num1;   //注意顺序，数栈下面的数，运算时放在前面
                break;
            case '-':
                res = num2-num1;
                break;
            default:
                break;
        }
        return res;
    }

    //判断是运算符还是整数
    public boolean isOper(int val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //判断字符优先级方法 , 假定 返回值的数字越大 优先级越高
    public int priority(int oper){
        if (oper == '*' || oper == '/') {
            return 1;
        }
        if (oper == '+' || oper == '-'){
            return 0;
        }else {
            return -1;  //假定，只做加减乘除
        }
    }

    //定义入栈操作
    public void push(int num){
        //先判断栈是否已满
        if (this.isFull()) {
            System.out.println("栈空间已满，不能再添加数据！");
            return;
        }
        top++;
        stack[top] = num;
    }

    //定义出栈操作:必须满足“先入后出”规律
    public int pop(){
        //先判断栈是否为空
        if (this.isEmpty()) {
            throw new RuntimeException("栈空，没有可以取出的数据！");
        }
        //栈若不为空
        int value = stack[top];
        top--;
        return value;
    }

    // 显示栈信息(遍历栈) 遍历时 需要从栈顶开始显示
    public void list(){
        //先判断栈是否为空
        if (this.isEmpty()) {
            throw new RuntimeException("栈为空，没有可以遍历的数据！");
        }
        //创建辅助指针，不能直接使用原头指针，否则遍历过后，原头指针就不再指向数组顶端了
        int temp = top;
        //若不为空，遍历打印
        System.out.println("栈中数据如下：");
        while (temp >= 0){
            System.out.printf("stack[%d]\n",stack[temp]);
            temp--;
        }
    }

}